Date: Wed, 20 Nov 1996 21:47:32 GMT
Server: NCSA/1.5
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<HTML VERSION="2.0">
<HEAD>
<!-- WEBMAGIC VERSION NUMBER="2.0.1" -->
<!-- WEBMAGIC TRANSLATION NAME="ServerRoot" SRC="/var/www/htdocs/" DST="/" -->
<!-- WEBMAGIC TRANSLATION NAME="ProjectRoot" SRC="./" DST="" -->
<TITLE>Computer Science 305 -- Fall 1996</TITLE>
</HEAD>
<BODY>
<P><LINK REV="made" HREF="mailto:dm@cs.bu.edu"><!-- Changed by: David Martin,  3-Nov-1995 --></P>
<H1><!WA0><IMG SRC="http://www.cs.bu.edu/lib/pics/bu-logo.gif"><BR>
 <!WA1><IMG SRC="http://www.cs.bu.edu/lib/pics/bu-label.gif"> <EM>Computer Science 305</EM><BR>
 <EM>Automata and Formal Languages</EM></H1>
<H3>Fall 1996 Syllabus</H3>
<P><EM>Last modified 11/19/96</EM></P>
<HR>
<P><!WA2><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw5/hw5.html">Click here for an HTML version of Homework 5, due on Tuesday, December 3.</A><BR>
<!WA3><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw5.ps">Click here for a postscript version of Homework 5.</A></P>
<P><!WA4><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw4/hw4.html">Click here for an HTML version of Homework 4, due on Friday, November 15.<BR>
 </A><!WA5><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw4.ps">Click here for a postscript version of Homework 4.</A></P>
<P><B>NOTE: be sure to fetch the attached figures below for a complete set of
solutions!</B><BR>
 <!WA6><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw3soln/hw3soln.html">Click here for an HTML version of the Homework 3 <B>solutions</B>.<BR>
 </A><!WA7><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw3fig.html">Click here for an HTML version of the Homework 3 <B>attached figures</B>.<BR>
 </A><!WA8><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw3soln.ps">Click here for a postscript version of the Homework 3 <B>solutions</B>.</A></P>
<P><!WA9><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw3/hw3.html">Click here for an HTML version of Homework 3, due on Tuesday, October 22.<BR>
 </A><!WA10><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw3.ps">Click here for a postscript version of Homework 3.</A></P>
<P><B>NEWS FLASH: Problem 4 cancelled in Homework #2!</B><BR>
 <!WA11><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw2/hw2.html">Click here for an HTML version of Homework 2, due on Thursday, October 10</A>.<BR>
 <!WA12><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw2.ps">Click here for a postscript version of Homework 2.</A></P>
<P><!WA13><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw1.ps">Click here for a postscript version of Homework 1, due on Thursday, September
26.</A> <BR>
 <!WA14><A HREF="http://www.cs.bu.edu/students/grads/dm/cs305/f96/hw1sol.ps">Click here for a postscript version of Homework 1 <B>solutions</B>.</A> The dfa diagrams are on the bulletin board outsise my office.</P>
<HR>
<H2>Instructor</H2>
<P><B>David Martin</B><BR>
 MCS 209 <BR>
 353-3326<BR>
 Click here to send mail to <!WA15><A HREF="mailto:dm@cs.bu.edu">dm@cs.bu.edu</A>. </P>
<H2>Office Hours</H2>
<P>Tuesday 2:10-3 pm<BR>
 Wednesday 1:30-2:00pm or later<BR>
 Thursday 4-5pm<BR>
 <I>and by appointment</I></P>
<H2>Classroom and Meeting Times</H2>
<P>Classes meet Tuesday and Thursday, 12:30pm - 2:00pm (i.e., 12:30pm - 1:50pm,
according to standard BU conventions) in MCS B23, the basement of 111 Cummington
St. </P>
<H2>Required Textbook</H2>
<P><EM>Introduction to the Theory of Computation (Preliminary Edition), </EM>Michael Sipser, PWS Publishing Company, 1996. See <!WA16><A HREF="http://www-math.mit.edu/~sipser/book.html">http://www-math.mit.edu/~sipser/errata.html</A> for an up-to-date list of errors in the book.</P>
<P>One copy of this book will be on reserve at the Science and Engineering
library after 9/10/96. I'll put another copy on reserve if I can find one.</P>
<P>You will read most of the textbook in this course.</P>
<H3>Other Useful Books</H3>
<UL>
<LI><EM>Elements of the Theory of Computation,</EM> Lewis &amp; Papadimitriou, Prentice Hall, 1981 
<LI><EM>Introduction to Automata Theory, Languages, and Computation,</EM> Hopcroft &amp; Ullman, Addison-Wesley, 1979 
</UL>
<H2>Prerequisites</H2>
<P>To enroll in this course, you must have satisified the following course
requirements. If you haven't done so but still want to remain in the course,
please see me. </P>
<UL>
<LI>MA 293 (Discrete Mathematics 1). 
<LI>CS 112 or CS 113 (Programming &amp; Data Structures in C). 
</UL>
<H2>Topics</H2>
<P>This course is a core requirement in undergraduate computer science curriculums
at most colleges. Its purpose is threefold; first, to encourage you to investigate
the nature of computation; second, to further develop your formal reasoning
and writing skills; and third, to add new techniques to your programming
bag of tricks. </P>
<P>Accordingly, we will develop several formal models of computation, each
more powerful than the last. At each stage we will prove some of what our
intuition suggests (and sometimes, what it denies) about these models. We
will also see how most models admit two very different characterizations:
one of machines that are able to recognize certain events, and another of
grammars that are able to generate exactly what these machines recognize. </P>
<P>In particular, we will study regular languages, regular expressions, finite
deterministic and nondeterministic automata, context-free grammars, pushdown
automata, turing machines --- and more, if time allows. </P>
<P></P>
<H2>Grading</H2>
<P>The following breakdown is tentative but reasonably representative of how
grades will be computed. I mentioned an optional project, but I haven't
decided how to fit that into the scheme yet.</P>
<PRE>
6 Homeworks    60%
Midterm        20%     Thursday, 10/24, 12:30-1:50pm
Final          20%     Tuesday, 12/17, 12:30-2:30 pm
</PRE>
<P>Note that each test is worth 2 homeworks. The tests will be much simpler
than the homeworks. </P>
<H2>Homework Assignments</H2>
<P>When writing up your homework, there are two goals you must keep in mind:
first, to give evidence that you have put real thought into the problem,
and second, to convince the reader that your solution is correct <EM>and that you know why</EM>. As a programmer, you have some experience with this sort of writing: an
effective program must be written for both a compiler and a human reader.
Similarly, solutions to your problems must be correct in the sense of solving
the stated problem, but they must also be comprehensible to the grader. </P>
<P>As with any writing, the first draft of a problem solution is usually unpresentable.
All of the pieces may be there, but they tend to be chaotically assembled. <EM>The single most important thing you can do</EM> to make your solutions presentable is to rewrite them after you have discovered
why they are correct, and then to throw away (or at least tuck away) your
initial draft. Remember, scratch paper is cheap. </P>
<P>Be careful to realize that this emphasis on presentation has nothing to
do with whether English is your native language or whether you prefer to
write your solutions with pencil, pen, quill, or word processor. A well-written
solution starts by stating assumptions and then works towards a clearly
defined goal, emphasizing the overall direction and omitting the superfluous. </P>
<P></P>
<H2>Late Policy</H2>
<P>In general, you will have at least one week to work on a homework assignment
and three opportunities to attend my office hours before that assignment
is due. </P>
<P>Assignments turned in during one of the two class periods following the
due date will be graded at 60% of their face value. Assignments turned in
later than that will receive no credit, but we'll still grade them for feedback
purposes.</P>
<H2>Collaboration and Plagiarism</H2>
<PRE>
col.lab.o.rate \k*-'lab-*-.ra-t\ \-.lab-*-'ra--sh*n\ \-'lab-*-.ra-t-iv\ 
   \-.ra-t-*r\ vi [LL collaboratus, pp. of collaborare to labor together, fr. 
   L com- + laborare to labor] 1: to work jointly with others esp. in an 
   intellectual endeavor 2: to cooperate with or assist usu. willingly an 
   enemy of one's country and esp. an occupying force 3: to cooperate with an 
   agency or instrumentality with which one is not immediately connected - 
   col.lab.o.ra.tion n
</PRE>
<P>Collaboration is encouraged (primarily in the first and third senses) when
working on homework problems and preparing for exams. None of the problems
in this class are intended to have secret solutions; the more resourceful
you are at discovering solutions, the more time you will have to write them
well. Indeed, if you are stuck on a problem, I will be happy to talk with
you about it during office hours. However, the solutions you turn in must
be your original writing. Copying a prepared solution is not collaboration
at all; it is plagiarism. </P>
<P></P>
<PRE>
pla.gia.rize \'pla--j*-.ri-z also -je--*-\ vt : to steal and pass off as 
   one's own (the ideas or words of another) to present as one's own an idea 
   or product derived from an existing source - pla.gia.riz.er n
</PRE>
<P>Plagiarizing another's words is not tolerated at Boston University. It is
so disdained that there are specific procedures for accusing and punishing
those who plagiarize. Do not copy another person's work and present it as
your own. </P>
<P>(The above definitions were copied from the Webster server at BU.) </P>
<P></P>
<H2>Attendance</H2>
<P>Attendance is not an official part of the course grade, but it is your responsibility
to stay informed. Some announcements will be made only in class. And, obviously,
it's easier to learn things from a teacher than directly from the book.
(Unless you hate the teacher.)</P>
<P></P>
<H2>Mailing List</H2>
<P>Other announcements will be made only by email. To add yourself to the course
mailing list, log on to a CS cluster computer (such as csa) and type </P>
<P></P>
<PRE>
    csmail -a cs305
</PRE>
<P><!WA17><IMG SRC="http://ei.cs.vt.edu/~history/ABC.GIF"> </P>
<P>The <!WA18><A HREF="http://www.cs.iastate.edu/cgi-bin/hit-count?jva/jva-archive.html">Atanasoff-Berry Computer (ABC)</A> of 1939, claimed to be the first electronic digital computer. Photo courtesy
of the <!WA19><A HREF="http://ei.cs.vt.edu/~history/">History of Computing Page</A> at Virginia Tech. </P>
<HR>
<P>Prepared by David Martin. Click <!WA20><A HREF="http://www.cs.bu.edu/courses/Home.html">here</A> for information on other courses. </P>
</BODY>
</HTML>
